package algorithm.bitmanipulation;

/**
 * leetcode : https://leetcode.com/problems/reverse-bits/description/
 * Diffculty: Easy
 *
 * 反转 一个23位无符号整数 的 bit位
 * 例如：
 * input:43261596       bitmanipulation: 00000010100101000001111010011100
 * output:964176192     bitmanipulation: 00111001011110000010100101000000
 *
 * 位运算的话，应该使用无符号位运算
 *
 * 解题思路：
 * https://leetcode.com/problems/reverse-bits/discuss/54746/Java-Solution-and-Optimization
 * https://blog.csdn.net/shine_zyd_way/article/details/52076180
 *
 * @Author Antony
 * @Since 2018/7/4 12:03
 */
public class ReverseBits {

    public static void main(String[] args) {
        Integer num_1 = 11111;
        System.out.println(Integer.toBinaryString(num_1));
        System.out.println(Integer.toBinaryString(reverseBits(num_1)));
//        System.out.println(Integer.valueOf("10100",2));

    }

    /**
     * (leetcode beats 72.07%)
     * 整体思路：
     * 把原数字n从右到左逐个取出位，然后tmp逐个往左移位，追加到最右边。就实现了反转
     *
     * (n >>> i) 是n无符号右移i位，
     * 然后和1与运算 就得到了第i位 的二进制字符 x
     *
     * 在改算法中，tmp 先左移，留出最右边的空位0
     * 然后空位0 和 x 或运算，就把x放到了空位上。
     *
     */
    // you need treat n as an unsigned value
    public static int reverseBits(int n) {
        int tmp=0;
        for(int i=0; i<32; i++){
            tmp <<= 1;              // tmp = tmp << 1;
            tmp |= (n >>> i) & 1;   // tmp = tmp | (n >>> i) & 1;
        }
        return tmp;
    }

    /**
     * (leetcode beats 72.07%)
     * 思路一样，另一种解法。
     * 每次 n 无符号右移一位以后改变n的值
     */
    public static int reverseBits_2(int n){
        int tmp = 0;
        for(int i=0; i<32; i++){
            tmp = (tmp<<1) + (n&1); //可以分开两步为: tmp <<=1; tmp +=(n&1);
            n >>>= 1;
        }
        return tmp;
    }
}
